home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / ingres04.lzh / source / iutil / bndxsearch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1985-01-23  |  5.1 KB  |  208 lines
  1. #
  2. # include    <sccs.h>
  3.  
  4. SCCSID(@(#)bndxsearch.c    8.1    12/31/84)
  5. /*
  6. **  BNDXSEARCH -- search an BTREE directory
  7. **    
  8. **    Looks for an available page, if this would force out a page from
  9. **    the relation it adds its own.  Searches each level of the dirctory
  10. **    for the lowest (highest) page on which the key could occur if mode
  11. **    is < (>) 0.  At each level the number of keys on the page is checked
  12. **    if it is <= SEARCHFUDGE a linear sharch is done, otherwize a binary
  13. **    search is preformed.  If the full key matches exactly the seach
  14. **    can stop.  Note that the keys tell the minimum value on that page.
  15. **
  16. **    Parameters:
  17. **        d    - pointer to descriptor of open relation
  18. **        tid    - returns tid of page to start (end) looking
  19. **        key    - to look for
  20. **        mode    - < 0 lowkey, > 0 hikey
  21. **        keyok    - true if all keys are assumed to be set
  22. **        path    - if non-null, is set to the tids of the access path
  23. **
  24. **    Returns:
  25. **        -2    - pageflush failure
  26. **        -1    - get_page failure
  27. **        0    - success
  28. **
  29. **    Side Effects:
  30. **        causes I/O
  31. **
  32. **    Requires:
  33. **        getpage, icompare, paramd, pageflush, top_acc, resetacc, etc.
  34. **
  35. **    Called By:
  36. **        find
  37. **
  38. **    History:
  39. **        Stolen from ndxsearch 7/26/80 (jiw)
  40. */
  41.  
  42. # include    <ingres.h>
  43. # include    <aux.h>
  44. # include    <symbol.h>
  45. # include    <access.h>
  46. # include    <lock.h>
  47.  
  48. # define    SEARCHFUDGE    6    /* # of linenos to do a binary search */
  49.  
  50. bndxsearch(d, tidx, tuple, mode, keyok, path)
  51. struct descriptor    *d;        
  52. struct tup_id        *tidx;        
  53. char            tuple[];    
  54. int            mode;    
  55. int            keyok;
  56. struct tup_id        *path;
  57. {
  58.     register struct tup_id        *tid;
  59.     register int            i;
  60.     long                pageid;
  61.     int                j, keylen, dno, partialkey;
  62.     char                *p;
  63.     int                pagerr;
  64.     struct accessparam        relparm;
  65.     int                top;
  66.     register            bottom;
  67.     extern char            *get_addr();
  68.  
  69.     tid = tidx;
  70.     pagerr = 0;
  71.     paramd(d, &relparm);    /* get domains in key order */
  72.  
  73.     /* assume fullkey is given */
  74.     partialkey = FALSE;
  75.  
  76.     /* remove any key domains not given by the user */
  77.     if (!keyok)
  78.     {
  79.         for (i = 0; dno = relparm.keydno[i]; i++)
  80.         {
  81.             if (d->relgiven[dno])
  82.                 continue;
  83.             relparm.keydno[i] = 0;
  84.             partialkey = TRUE;
  85.             printf("partial key true\n");
  86.             break;
  87.         }
  88.     }
  89.  
  90.     /* if the first key isn't given, just return else search directory */
  91.     if (relparm.keydno[0] != 0)
  92.     {
  93.         /* The actual BTREE directory search must be performed */
  94.         pageid = 0;        /* BTREE root is page 0 */
  95.         stuff_page(tid, &pageid);
  96.  
  97.         Acclock = FALSE;
  98.  
  99.         do
  100.         {
  101.             if (path)
  102.             {
  103.                 bmove(tid, path++, sizeof(struct tup_id));
  104.             }
  105.  
  106.             if (pagerr = get_page(d, tid))
  107.                 break;    /* fatal error */
  108.             Acc_head->bufstatus |= BUF_DIRECT;  /* don't get confused */
  109.             bottom = -1;
  110.             top = Acc_head->nxtlino - 1;
  111.             if (top >= SEARCHFUDGE)  /* we are past breakeven */
  112.             {
  113.                 printf("doing binary search\n");
  114.                 while (top != bottom)    /* binary search */
  115.                 {
  116.                     tid->line_id = ((1 + top - bottom) >> 1) + bottom;    /* get to half way point */
  117.                     p = get_addr(tid) + PGPTRSIZ;
  118.                     for (j = 0; dno = relparm.keydno[j]; j++)
  119.                     {
  120.                         keylen = d->relfrml[dno] & I1MASK;
  121.                         printf("data: ");
  122.                         printatt(d->relfrmt[dno], keylen, p);
  123.                         printf("| compared with: ");
  124.                         printatt(d->relfrmt[dno], keylen, &tuple[d->reloff[dno]]);
  125.                         printf("|\n");
  126.                         if (i = icompare(&tuple[d->reloff[dno]], p, d->relfrmt[dno], keylen))
  127.                             break;
  128.                         p += keylen;
  129.                     }
  130.                     /* if key is below directory, then we are in the bottom half */
  131.                     printf("i = %d, mode %d, partialkey %d, top %d, bottom %d\n", i, mode, partialkey, top, bottom);
  132.                     if (i < 0 || (i == 0 && partialkey && mode < 0))
  133.                         top = tid->line_id - 1;
  134.  
  135.                     else if (i == 0 && !partialkey)
  136.                     {
  137.                         bottom = tid->line_id;
  138.                         break;
  139.                     }
  140.                     else
  141.                         bottom = tid->line_id;
  142.                 }
  143.             }
  144.             else    /* do a linear search */
  145.             {
  146.                 printf("doing linear search\n");
  147.                 for (tid->line_id = 0; (tid->line_id & I1MASK) < Acc_head->nxtlino; tid->line_id++)
  148.                 {
  149.                     printf("inside loop: tid\n");
  150.                     dumptid(tid);
  151.                     p = get_addr(tid) + PGPTRSIZ;
  152.                     for (i = 0; dno = relparm.keydno[i]; i++)
  153.                     {
  154.                         keylen = d->relfrml[dno] & I1MASK;
  155.                         printf("data: ");
  156.                         printatt(d->relfrmt[dno], keylen, p);
  157.                         printf("| compared with: ");
  158.                         printatt(d->relfrmt[dno], keylen, &tuple[d->reloff[dno]]);
  159.                         printf("|\n");
  160.                         if (j = icompare(&tuple[d->reloff[dno]], p, d->relfrmt[dno], keylen))
  161.                             break;
  162.                         printf("after break in tuple comp\n");
  163.                         p += keylen;
  164.                     }
  165.                     /* if key is below directory, then we have passed the position */
  166.  
  167.                     printf("j = %d, mode %d, partialkey %d\n", j, mode, partialkey);
  168.                     if (j < 0)
  169.                         break;
  170.  
  171.                     /* if lowkey search on partial key matches, then done */
  172.                     if (j == 0 && partialkey && mode < 0)
  173.                         break;
  174.                     if (j == 0 && mode < 0)
  175.                     {
  176.                         break;
  177.                     }
  178.                 }
  179.             }
  180.             if (bottom < 0)
  181.                 p = Acc_head->firstup;
  182.             else
  183.             {
  184.                 tid->line_id = bottom;
  185.                 p = get_addr(tid);
  186.             }
  187.             printf("result: ");
  188.             dumptid(tid);
  189.             bmove(p, tid, PGPTRSIZ);
  190.             printf("and next tid: ");
  191.             dumptid(tid);
  192.         } while (Acc_head->mainpg);  /* if at level zero then done */
  193.         Acclock = TRUE;
  194.     
  195.     }
  196.     tid->line_id = -1;
  197.  
  198.     if (path)
  199.     {
  200.         bmove(tid, path++, sizeof(struct tup_id));
  201.         path->line_id = -2;        /* impossible value */
  202.     }
  203.  
  204.     printf("final: ");
  205.     dumptid(tid);
  206.     return (pagerr);
  207. }
  208.